package com.xiaoyu.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @program: DS_and_A
 * @description:
 * 给定一个三角形 triangle ，找出自顶向下的最小路径和。
 *
 * 每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是 下标 与 上一层结点下标 相同
 * 或者等于 上一层结点下标 + 1 的两个结点。
 * 也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。
 *
 *
 * 输入：triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
 * 输出：11
 * 解释：如下面简图所示：
 *    2
 *   3 4
 *  6 5 7
 * 4 1 8 3
 * 自顶向下的最小路径和为11（即，2+3+5+1= 11）。
 *
 * @author: YuWenYi
 * @create: 2021-05-27 17:51
 **/

/*
      错误解法:每次都只选择最小的那个,有时候不一定这次选的是小的,之后就是小的!
      例如如下情况,最小路径是-1,但是如果每次都按最小的找,找出的最小路径却是0,从而发生错误!
          -1
        2    3
      1  -1  -3
*     int len = triangle.size();
        int[] dp = new int[len];
        dp[0] = triangle.get(0).get(0);
        int index = 0;
        //从第二层开始寻找最小路径
        for (int i = 1; i < len; i++) {
            List<Integer> row = triangle.get(i);
            int min = Math.min(row.get(index), row.get(index + 1));
            index = min == row.get(index) ? index : index+1;
            dp[i] = min + dp[i-1];
        }
        return dp[len-1];
*
* */
public class MinimumTotal_120 {


    //解法一:回溯法  --->   不出所料,又超时了!!!!
    int miniSum;
    boolean flag = true;
    public int minimumTotal(List<List<Integer>> triangle) {
        int len = triangle.size();
        if (len == 1) return triangle.get(0).get(0);
        int pathSum = triangle.get(0).get(0);
        dfs(triangle, len, pathSum, 1,0);
        return miniSum;
    }

    public void dfs(List<List<Integer>> triangle,int len,int pathSum,int layer,int begin){
        if (layer == len){
            if (flag){ //第一次进来的时候,直接将第一条路径的长度给它就可以了
                miniSum = pathSum;
                flag = false;
            }else {  //后面每次进来都取最小路径
                miniSum = Math.min(miniSum, pathSum);
            }
            return;
        }

        List<Integer> list = triangle.get(layer);
        for (int i = begin; i <= begin + 1; i++) {
            pathSum = pathSum + list.get(i);
            dfs(triangle, len, pathSum, layer+1,i);
            pathSum = pathSum - list.get(i);
        }
    }



    //解法二:DP
    /*
    * 用 f[i][j] 表示从三角形顶部走到位置 (i,j) 的最小路径和。
    * 这里的位置 (i, j) 指的是三角形中第 i 行第 j 列（均从 0 开始编号）的位置。
    *
    * 动态转移方程: f[i][j]=min(f[i−1][j−1],f[i−1][j])+c[i][j]
    * 当 j=0时: f[i][0]=f[i−1][0]+c[i][0]
    * 当 j=i时: f[i][i]=f[i−1][i−1]+c[i][i]
     *
    * 每一行的数据个数为 --> i+1个
    *
    * 原先我使用的应该是贪心,用在这题是完全错误的!!!
    * 这题的含义是:当你走到某个点,那么你需要去加上你能选择的已经走过的两条路已经已经确定较小的那条!
    *
    *设三角形为:
    *     -1                             -1
    *    2   3     --->  dp数组中:     1     2
    * -1   3  -3                    0    4    -1
    *                            最后再找出最后一层中最小的数字即可!!
    *
    * 即计算了len条最小路径,然后在这里面再选出最小的出来!
    * 由杨辉三角的特性,下一层的某点的值是上层点的该位置值+上层该位置-1的点的值
    * 由于dp数组中保存的就是一个这样的杨辉三角,因此有这样的特性!
    * */
    public int minimumTotal1(List<List<Integer>> triangle) {
        int len = triangle.size();
        int[][] dp = new int[len][len];
        dp[0][0] = triangle.get(0).get(0);
        for (int i = 1; i < len; i++) {
            dp[i][0] = dp[i-1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                dp[i][j] = Math.min(dp[i-1][j-1],dp[i-1][j]) + triangle.get(i).get(j);
            }
            dp[i][i] = dp[i-1][i-1] + triangle.get(i).get(i);
        }
        int minPath = dp[len - 1][0];
        for (int i = 1; i < dp[len - 1].length; i++) {
            minPath = Math.min(dp[len-1][i],minPath);
        }
        return minPath;
    }

    //解法三:逆序DP  -->  将三角形倒着找路径dp[i][j]=min(dp[i+1][j],dp[i+1][j+1])+triangle[i][j]
    /*
    * 每次循环减少一条路,到最后就剩下了唯一的一条最短路径了
    * 设三角形为:
    *     -1                             -1
    *    2   3     --->  dp数组中:      1   0
    * -1   3  -3                    -1   3   -3
    *                             0    0   0    0
    * 将最小值归于一点,真是牛逼!
    * */
    public int minimumTotal2(List<List<Integer>> triangle) {
        int len = triangle.size();
        //因为最后一行需要找它下面的那行,所以dp的长度需要+1,三角形最后一行可以加它的下一行的值(值全是0,加了和没加一样)
        int[][] dp = new int[len + 1][len + 1];
        for (int i = len - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[i][j] = Math.min(dp[i+1][j],dp[i+1][j+1]) + triangle.get(i).get(j);
            }
        }
        return dp[0][0];
    }


    //解法四: 了解  递归是触底后才开始反弹再将路径相加,因此其等价于解法3
    //递归 + 记忆化  递归公式为:f(i,j)=min(f(i+1,j),f(i+1,j+1))+triangle[i][j]
    static Integer[][] memo;
    public int minimumTotal3(List<List<Integer>> triangle) {
        memo = new Integer[triangle.size()][triangle.size()];
        return  dfs(triangle, 0, 0);
    }

    private int dfs(List<List<Integer>> triangle, int i, int j) {
        if (i == triangle.size()) {
            return 0;
        }
        if (memo[i][j] != null) {
            return memo[i][j];
        }
        return memo[i][j] = Math.min(dfs(triangle, i + 1, j), dfs(triangle, i + 1, j + 1)) + triangle.get(i).get(j);
    }


    //解法五:  解法三的空间优化版!
    public int minimumTotal4(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[] dp = new int[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                dp[j] = Math.min(dp[j], dp[j + 1]) + triangle.get(i).get(j);
            }
        }
        return dp[0];
    }




    public static void main(String[] args) {
        MinimumTotal_120 m120 = new MinimumTotal_120();
        List<List<Integer>> triangle = new ArrayList<>();
        triangle.add(new ArrayList<Integer>(){{add(-1);}});
        triangle.add(new ArrayList<Integer>(){{add(2); add(3);}});
        triangle.add(new ArrayList<Integer>(){{add(-1); add(3);add(-3);}});
        triangle.add(new ArrayList<Integer>(){{add(-3); add(1);add(4);add(-3);}});
        System.out.println(m120.minimumTotal4(triangle));
        for (Integer[] integers : memo) {
            for (Integer integer : integers) {
                System.out.print(integer+" ");
            }
            System.out.println();
        }
    }
}
